/*
规则：每人TOTCARD／2 张牌 ，A先出 ，大牌压小牌 ， 出光的赢
*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <string.h>
using namespace std;
const int LEN = 10;
const int TOTCARD=6;
const int INF = TOTCARD*10;
const int DEEP=7;
class Pair{
public:
	int id;
	int val;
	Pair(){
		id=0;
		val=0;
	}
};
class Mypos{
public:
	int step;
	bool isA;
	vector<int> a;
	vector<int> b;
	vector<bool> ua;
	vector<bool> ub;
	vector<int> aout;
	vector<int> bout;
	Mypos(){
		step=0;
		isA=true;
		int i;
		for (i=0;i<=TOTCARD;i++){
			ua.push_back(false);
			ub.push_back(false);
		}
	}
	void show();
	vector<int> gen();
	void cmd(char ,int);
	bool win();
	int calc();
	int negcalc();
};
Mypos root;
void init();
bool comfirm();
bool win(const Mypos& pos);
void astep();
void bstep();
void showcan(vector<int> &);
int dfs(int,int & , Mypos & );
Pair abdfs(int,Pair , Mypos & ,int ,int );
int negdfs(int,int & , Mypos & );
int main(){
	bool goon=true;
	while (goon){
		/*
			人int先手，电脑后出
			A         B
		*/
		init();
		root.show();

		while (true){
			if (root.win()){
				printf("B is winner at %d steps\n",root.step);
				break;
			}
			//A
			astep();
			//
			if (root.win()){
				printf("A is winner at %d steps\n",root.step);
				break;
			}
			//B
			bstep();
			//

		}
		goon=comfirm();
	}
	return 0;
}
vector<int> Mypos::gen(){
	vector<int> ret;
	int i;

	if (isA){
		//printf("A is preparing data\n");
		for (i=1;i<=TOTCARD;i++){
			if (!ua[i]){
			    /*
				if (step>=1){
					if (i>bout[step-1])
						ret.push_back(i);
				}else{
					ret.push_back(i);
				}
				*/
                int len=bout.size();
                if (len>0){
                    if (i>bout[len-1])
						ret.push_back(i);
                }else{
                    ret.push_back(i);
                }
			}
		}
	}else{
		//printf("B is preparing data\n");
		for (i=1;i<=TOTCARD;i++){
			if (!ub[i]){
				    /*
		        	if (i>aout[step])
		            ret.push_back(i);
		            */
		        	int len=aout.size();
		        	if (len>0){
		            		if (i>aout[len-1])
						ret.push_back(i);
		        	}else{
		            		ret.push_back(i);
		        	}
            		}
		}
	}
    /*
        这里A ,B 处理是不一样的 ，由于B去更新step ,可以用aout.size() 去A ,最后出的牌
    */
	ret.push_back(0);
	return ret;
}
void Mypos::cmd(char pep,int val){
	if (isA){
		ua[val]=true;
		aout.push_back(val);
	}else{
		ub[val]=true;
		bout.push_back(val);
		step++;
	}
	isA=!isA;
}
void astep(){
	int next;
	int i;
	printf("please choose a card:\n");
	vector<int> can=root.gen();
	bool ok=false;
	while (!ok){
		showcan(can);
		scanf("%d",&next);
		if (next>=0&&next<=TOTCARD){
		    for (i=0;i<can.size();i++)
		        if (can[i]==next){
		            ok=true;
		            break;
		        }
		}
	}
	printf("your choice %d .\n",next);
	root.cmd('A',next);
	root.show();
}

void bstep(){

	/*手动
	int next;
	int i;
	printf("please choose a card:\n");
	vector<int> can=root.gen();
	bool ok=false;
	while (!ok){
		showcan(can);
		scanf("%d",&next);
		for (i=0;i<can.size();i++)
			if (can[i]==next){
				ok=true;
				break;
			}
	}
	printf("B choice %d .\n",next);
	root.cmd('B',next);
	root.show();
	*/
	/*
	自动
	*/
	vector<int> can=root.gen();
	showcan(can);

	Pair next;//下一步出的牌
	Mypos tpos = root;
	next=abdfs(DEEP,next,tpos,-INF,INF);
	//negdfs(DEEP,next,tpos);
	int i;
	bool ok=false;
	for (i=0;i<can.size();i++)
			if (can[i]==next.id){
				ok=true;
				break;
			}
	if (ok==false){
		printf("error cmd debug please!\n");
	}
	printf("B choice %d .\n",next.id);
	root.cmd('B',next.id);
	root.show();
}
int dfs(int lev,int & next, Mypos & pos){
	if (pos.win()){
		return pos.calc();
	}else if (lev<=0){
		return pos.calc();
	}
	int val;
	if (pos.isA){//min
		//对手下 ， 要取子节点中最小的
		val=INF;
	}else{//max
		//自己下 ，要取子节点中最大的
		val=-INF;
	}
	vector<int> can=pos.gen();
	//showcan(can);
	int i;
	Mypos mem = pos;
	for (i=0;i<can.size();i++){
		pos.cmd('X',can[i]);//产生子节点,前面参数没用
		int chv = dfs(lev-1,next,pos);
		pos=mem;
		if (pos.isA){//对手下 ， 要取子节点中最小的
			if (chv<val){
				next=can[i];
				val=chv;
			}
		}else{//自己下 ，要取子节点中最大的
			if (chv>val){
				next=can[i];
				val=chv;
			}
		}
	}
	return val;
}
//alp 是下限 ， beta是上限  alp<beta
Pair abdfs(int lev, Pair next,Mypos & pos,int alp ,int beta){
    /*
        发现问题，next 由于 被下层覆盖,返回错误值
    */
	printf("(%d ,%d)\n",alp,beta);
	pos.show();
	if (pos.win()){
		next.val=pos.calc();
		return next;
	}else if (lev<=0){
		next.val=pos.calc();
		return next;
	}
	int val;
	vector<int> can=pos.gen();//用pos ,不是root
	showcan(can);
	int i;
	Mypos mem = pos;
	Pair ret=next;
	for (i=0;i<can.size();i++){
		pos.cmd('X',can[i]);//产生子节点,前面参数没用
        	next.id=can[i];
        	next.val=0;
		Pair tmp = abdfs(lev-1,next,pos,alp,beta);
		int chv = tmp.val;
		pos=mem;
		if (pos.isA){//对手下 ， 要取子节点中最小的
			if (chv<beta){
				/*
                    relax beta
				*/
				beta=chv;
				if (alp>=beta){
                    ret.id=can[i];
                    ret.val=alp;
					return ret;
				}
				ret.id=can[i];
				ret.val=beta;
			}
		}else{//自己下 ，要取子节点中最大的
			if (chv>alp){
				alp=chv;
				if (alp>=beta){
                    			ret.id=can[i];
                    			ret.val=beta;
					return ret;  //im
				}
                		ret.id=can[i];
				ret.val=beta;
			}
		}
	}
	return ret;
}
int negdfs(int lev,int & next, Mypos & pos){
	if (pos.win()){
		return pos.negcalc();
	}else if (lev<=0){
		return pos.negcalc();
	}
	int val;
	val=-INF;
	vector<int> can=pos.gen();
	//showcan(can);
	int i;
	Mypos mem = pos;
	for (i=0;i<can.size();i++){
		pos.cmd('X',can[i]);//产生子节点,前面参数没用
		int chv = -1*negdfs(lev-1,next,pos);
		pos=mem;
		if (chv>val){
			next=can[i];
			val=chv;
		}
	}
	return val;
}
int Mypos::calc(){//估价函数
	int i;
	int cnt=0;
	//总数 － 剩下的牌数
	for (i=0;i<a.size();i++){
		if (ua[a[i]]==false){
			cnt++;
		}
	}
	int va = TOTCARD-cnt;

	cnt=0;
	for (i=0;i<b.size();i++){
		if (ub[b[i]]==false){
			cnt++;
		}
	}
	int vb = TOTCARD-cnt;
	int val = vb-va;
	if (val>0)
		val+=3;
	else
		val-=3;
	return val;
}
int Mypos::negcalc(){
	int i;
	int cnt=0;
	//总数 － 剩下的牌数
	for (i=0;i<a.size();i++){
		if (ua[a[i]]==false){
			cnt++;
		}
	}
	int va = TOTCARD-cnt;

	cnt=0;
	for (i=0;i<b.size();i++){
		if (ub[b[i]]==false){
			cnt++;
		}
	}
	int vb = TOTCARD-cnt;
	int val;
	if (isA){
		val = va-vb;
	}else{
		val = vb-va;
	}
	return val;
}
bool Mypos::win(){//whowin
	bool ok=true;
	int i;
	if (isA){//A出牌 检查B
		//printf("A is choosing card , check B \n");
		ok=true;
		for (i=0;i<b.size();i++){
			if (ub[b[i]]==false){
				//printf("find %d is available!\n",b[i]);
				ok=false;
				break;
			}
		}
		if (ok){
			//printf("B is winner at %d steps\n",step);
		}
	}else{
		//printf("B is choosing card , check A\n");
		ok=true;
		for (i=0;i<a.size();i++){
			if (ua[a[i]]==false){
				//printf("find %d is available!\n",a[i]);
				ok=false;
				break;
			}
		}
		if (ok){
			//printf("A is winner at %d steps\n",step);
		}
	}
	//ok=true;
	if (!ok){
		//printf("Go on!\n");
	}
	return ok;
}
bool comfirm(){
	return false;
}
void init(){
	srand(time(NULL));
	bool used[TOTCARD+5];
	memset(used,false,sizeof(used));
	Mypos ret;
	int half = TOTCARD/2;
	int i;
	for (i=0;i<half;i++){
		bool find=false;
		int val;
		while (!find){
			 val = (rand()%TOTCARD)+1;
			if (!used[val]){
				used[val]=true;
				find=true;
			}
		}
		ret.a.push_back(val);
		
		find=false;
		while (!find){
			 val = (rand()%TOTCARD)+1;
			if (!used[val]){
				used[val]=true;
				find=true;
			}
		}
		ret.b.push_back(val);
		
	}
	
	int a[]={2,4,5};
	int b[]={1,3,6};
	/*
		a:5 4 0 0
		b:0 6 3 1
		
		a:5 0 4 2
		b:6 3 0	 
	*/
	ret.a = vector<int>(a,a+3);
	ret.b = vector<int>(b,b+3);
	ret.aout.clear();
	ret.bout.clear();
	for (i=0;i<ret.ua.size();i++){
		ret.ua[i]=ret.ub[i]=false;
	}
	for (i=0;i<ret.a.size();i++){
		ret.ub[a[i]]=true;
	}
	for (i=0;i<ret.b.size();i++){
		ret.ua[b[i]]=true;
	}
	root = ret;
}

void Mypos::show(){
	int i;
	printf("==================\n");
    printf("step: %d\n",step);
	if (isA){
		printf("A turn\n");
	}else{
		printf("B turn\n");
	}
	printf("A has cards:\n");
	for (i=0;i<a.size();i++){
		printf(" %d ",a[i]);
	}
	printf("\n");

	for (i=0;i<a.size();i++){
		printf("card: %d  is ok: %d\n",a[i],!ua[a[i]]);
	}
	printf("\n");

	printf("B has cards:\n");
	for (i=0;i<b.size();i++){
		printf(" %d ",b[i]);
	}
	printf("\n");

	for (i=0;i<a.size();i++){
		printf("card: %d  is ok: %d\n",b[i],!ub[b[i]]);
	}
	printf("\n");

	printf("match\n");
	printf("A: ");
	for (i=0;i<aout.size();i++){
		printf(" %d ",aout[i]);
	}
	printf("\n");

	printf("B: ");
	for (i=0;i<bout.size();i++){
		printf(" %d ",bout[i]);
	}
	printf("\n");

	printf("==================\n\n");
}

void showcan(vector<int> & v){
	printf("can choose :\n");
	for (int i=0;i<v.size();i++){
		printf(" %d ",v[i]);
	}
	printf("\n");
}



